from collections import defaultdict
from PyLinkedList import Node, LinkedList

class FibHeap:
    Instances = []

    def __init__(self, heaptype='min'):
        # Distinguish  a node versus an element: a node is explicitly a Node instance
        # which has a key and can contain additional data.  An element is part of the
        # FibHeap API which consists of a sequence (data, priority), irrelevant of
        # linked list implementation. Coincidentally, the key and data for a node here
        # are str(element), element respectively.

        # Variable nodes will be a dictionary, with the keys being elements in the heap.
        # The value for each key will be a dictionary holding attributes for that element.
        # The attributes are: parent(Node), child(Node), degree(Int), mark(Bool), priority(Int), node(Node)
        self.nodes = defaultdict(dict)
        self.rootsList = None           # Initialize, heap (and therefore root list) is empty initially
        self.maxPriorityNode = None     #
        self.num_nodes = 0              #
        self.num_trees = 0              #
        self.num_marks = 0              #
        self.heaptype = heaptype
        if heaptype != 'max':
            self.heaptype = 'min'

    def maxPrority(self):
        pass

    def fHeapPush(self, element):
        pass

    def fHeapInsert(self, element):
        # Unpack the received element (a sequence) to value, priority, and repack into a tuple
        value, priority = element
        element = (value, priority)

        # If the element is not already in the heap, allocate a node for the element
        # and store it in our dictionary.  Check if the heap is empty or not, in order to
        # allocate a new linked list or just append the node to a side of the max priority node
        if not self.exists(value):
            node = Node(str(element), element)
            self._addToHash(value, priority, node)
            if self.isEmpty():
                self.rootsList = LinkedList('circular')
                self.maxPriorityNode = node
                self.rootsList.insertNode(node)
            else:
                self.rootsList.insertNodeAfter(self.maxPriorityNode, node)
                if self._isGreaterPriority(element, self.maxPriorityNode.data()):
                    self.maxPriorityNode = node
            self.num_nodes += 1
        else:
            # self.takeAction() future feature
            self.fHeapChangePriority(value, priority)

    def fHeapPop(self):
        # Check if the heap is empty or not.  If it's not, append all the children
        # of maxNode to the rootlist.  If maxNode was the only node in the heap,
        # Set the new max to None else just tentatively pick the next node in
        # the root list and post-process the heap to fix it
        #import pdb
        #pdb.set_trace()
        maxNode = self.maxPriorityNode      # Local alias
        value, priority = maxNode.data()    # Unpack element
        if not self.isEmpty():
            self._appendNodesToRoot(self.nodes[value]['child'])
            self._delete(maxNode)
            if maxNode == maxNode.next():
                self.maxPriorityNode = None
            else:
                self.maxPriorityNode = maxNode.next()
                self._processRootList()
            self.num_nodes -= 1
        # Note: no error if heap is empty, None is returned instead
        return maxNode

    def fHeapChangePriority(self, value, priority):
        pass#data, newPriority

    def fHeapUnion(self, otherHeap):
        newHeap = FibHeap()
        newHeap.maxPriorityNode = self.maxPriorityNode
        newHeap.rootsList = map(lambda x: x, otherHeap.rootsList)
        otherMax = otherHeap.maxPriorityNode
        if self.isEmpty() or (otherMax != None and self._isGreaterPriority(otherMax.data(), self.maxPriorityNode.data())):
            newHeap.maxPriorityNode = otherMax
        newHeap.num_nodes = self.num_nodes + otherHeap.num_nodes
        otherHeap = newHeap # check
        return newHeap

    def exists(self, value, want_priority=False):
        if want_priority == False:
            return value in self.nodes.keys()
        if value in self.nodes.keys():
            return self.nodes[value]['node']
        return None

    def isEmpty(self):
        return self.num_nodes == 0


    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+        Helper          *+*+*+*#
    #+*+*+*+       Functions        *+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    def _isGreaterPriority(self, elementA, elementB):
        if self.heaptype == 'max':
            return elementA[1] > elementB[1]
        return elementA[1] < elementB[1]

    def _addToHash(self, value, priority, node):
        self.nodes[value]['degree']    = 0
        self.nodes[value]['parent']    = None
        self.nodes[value]['child']     = None
        self.nodes[value]['mark']      = False
        self.nodes[value]['priority']  = priority
        self.nodes[value]['node']      = node

    def _appendNodesToRoot(self, node):
        if node == None:
            return
        for _dummy in self._traverseList():
            self._appendToRoot(node)
            node = node.next()
        #appendComplete = False
        #node = startNode
        #endkey = node.prev().key()
        #while appendComplete == False:
        #    self._appendToRoot(node)
        #    if node.key() == endkey:
        #        appendComplete = True
        #    node = node.next()

    def _appendToRoot(self, node):
        value, priority = node.data()
        LinkedList.delete(node)
        self.rootsList.insertNodeAfter(self.maxPriorityNode, node)
        self.nodes[value]['parent'] = None

    def _processRootList(self):
        Degrees = [None] * self.num_nodes           # Array to keep track of nodes with clashing degrees
        for nodeA in self._traverseList():
            elementA          = nodeA.data()
            valueA, priorityA = elementA            # Fetch the key for our internal dictionary
            degreeA           = self.nodes[valueA]['degree']    # And fetch current node's degree
            while Degrees[degreeA]:                 # While there's clashing nodes with our current node...
                nodeB = Degrees[degreeA]            # remove the node with the lower priority from the roots list
                elementB          = nodeB.data()    # and make it a child of the other one
                valueB, priorityB = elementB
                if self._isGreaterPriority(elementA, elementB): self._moveToAsChild(nodeA, nodeB)
                else: self._moveToAsChild(nodeB, nodeA)
                Degrees[degreeA] = None
                degreeA += 1
            Degrees[degreeA] = nodeA
        self.maxPriorityNode = None
        for degree in xrange(len(Degrees)):
            if not Degrees[degree]:
                continue
            node = Degrees[degree]
            element = node.data()
            if self.isEmpty():
                self.rootsList = LinkedList('circular')
                self.maxPriorityNode = node
                self.rootsList.insertNode(node)
                return
            self.rootsList.insertNodeAfter(self.maxPriorityNode, node)
            if self._isGreaterPriority(element, self.maxPriorityNode.data()):
                self.maxPriorityNode = node

    def _moveToAsChild(self, parent, toChild):
        self._delete(toChild)   # Remove node to be linked from root list
        parentValue, childValue = parent.data()[0], toChild.data()[0] # Fetch dictionary keys
        self.nodes[parentValue]['child'] = toChild
        self.nodes[parentValue]['degree'] += 1
        self.nodes[childValue]['parent'] = parent
        self.nodes[childValue]['mark'] = False

    def _traverseList(self):
        return self.rootsList._traverseList()

    def _delete(self, node):
        self.rootsList.delete(node)

# Implements a binomial heap. Can be 'minimum' or 'maximum'
class BinHeap:

    Instances = []

    def __init__(self, HList=[], heaptype='max'):
        self.list = map(lambda elem: elem, HList)
        self.heapsize = len(self.list) - 1
        self.heaptype = heaptype
        self.heapfunc = BinHeap.maxBinHeapify
        if heaptype != 'min' and heaptype != 'max':
            self.heaptype = 'max'
        if self.heaptype == 'min':
            self.heapfunc = BinHeap.minBinHeapify
        BinHeap.Instances.append(self)
        self.buildBinHeap()

    def getAllInstances(self):
        if len(BinHeap.Instances) > 0:
            return BinHeap.Instances
        return 'Empty!'

    def setList(self, List):
        self.list = map(lambda elem: elem, List)
        self.heapsize = len(self.list) - 1
        self.buildBinHeap()

    def getList(self):
        return self.list

    def printList(self):
        return self.list

    def setBinHeapsize(self, heapsize):
        self.heapsize = heapsize

    def getBinHeapsize(self):
        return self.heapsize

    def setBinHeaptype(self, Type):
        if Type == 'max' or Type == 'min':
            self.heaptype = Type
        else:
            self.heaptype = 'max'
        if self.heaptype == 'max':
            self.heapfunc = BinHeap.maxBinHeapify
        else:
            self.heapfunc = BinHeap.minBinHeapify
        self.buildBinHeap()

    def getBinHeaptype(self):
        return self.heaptype

    def getBinHeapfunc(self):
        return self.heapfunc


    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    def heapPush(self, element):
        self.heapInsert(element)

    def heapPop(self):
        self.swap(0, self.heapsize)
        element = self.list.pop()
        self.heapsize -= 1
        heapfunc = self.heapfunc
        heapfunc(self, 0)
        return element

    def heapInsert(self, element):
        myelem = map(lambda x: x, list(element))
        self.list.append(float('inf'))
        self.heapsize += 1
        self.heapIncreasePriority(self.heapsize, myelem)

    def heapIncreasePriority(self, index, element):
        self.setValue(index, element)
        if self.getBinHeaptype() == 'max':
            while index > 0 and self.getValue(self.getParent(index))[1] < self.getValue(index)[1]:
                self.swap(index, self.getParent(index))
                index = self.getParent(index)
        else:
            while index > 0 and self.getValue(self.getParent(index))[1] > self.getValue(index)[1]:
                self.swap(index, self.getParent(index))
                index = self.getParent(index)


    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    def swap(self, i, j):
        self.list[i], self.list[j] = self.list[j], self.list[i]

    def setValue(self, index, value):
        self.list[index] = value

    def getValue(self, index):
        return self.list[index]

    def getParent(self, index):
        return int((index - 1) / 2)

    def getLeft(self, index):
        return (index * 2) + 1

    def getRight(self, index):
        return (index * 2) + 2


    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#


    def buildBinHeap(self, List=None):
        if List:
            self.setList(List)
        elif len(self.list) == 0:
            return self.list

        heapfunc = self.heapfunc
        for index in xrange(int(self.heapsize / 2), -1, -1):
            heapfunc(self, index)

    def maxBinHeapify(self, index):
        heapsize= self.heapsize
        largest = None
        left    = self.getLeft(index)
        right   = self.getRight(index)

        if left <= heapsize and self.getValue(left)[1] > self.getValue(index)[1]:
            largest = left
        else:
            largest = index
        if right <= heapsize and self.getValue(right)[1] > self.getValue(largest)[1]:
            largest = right
        if index != largest:
            self.swap(index, largest)
            self.maxBinHeapify(largest)
            return

    def minBinHeapify(self, index):
        heapsize= self.heapsize
        smallest = None
        left    = self.getLeft(index)
        right   = self.getRight(index)

        if left <= heapsize and self.getValue(left)[1] < self.getValue(index)[1]:
            smallest = left
        else:
            smallest = index
        if right <= heapsize and self.getValue(right)[1] < self.getValue(smallest)[1]:
            smallest = right
        if index != smallest:
            self.swap(index, smallest)
            self.maxBinHeapify(smallest)
            return

    def destroy(self):
        BinHeap.Instances= filter(lambda instance: self != instance, BinHeap.Instances)
